Relational and object-relational database management systems store information in tables of rows in a database. To retrieve data, queries that request data are submitted to a database server, which computes the queries and returns the data requested.
Queries submitted to the database server must conform to the syntactical rules of a particular query language. One popular query language, known as the Structured Query Language (SQL), provides users a variety of ways to specify information to be retrieved.
A query submitted to a database server is evaluated by a query optimizer. Based on the evaluation, the query optimizer generates an execution plan that defines operations for executing the query. Typically, the query optimizer generates an execution plan optimized for efficient execution. The optimized execution plan may be based on a rewrite of the query.
A query may specify a full outer join operation based on join condition between two tables, a left table and a right table. A full outer join joins every row in the left table with every row in the right table that satisfies the join condition. A full outer join also returns a row for each row in the left table that did not satisfy the join condition with any row in the right table, and returns a row for any row in the right table that did not satisfy the join condition with any row in the left table.
The following tables are used to illustrate a full outer join.
TABLE EMPROW #DEPTNODNAME110SALES230MARKET
TABLE DEPTROW #EMPNOENAMEDEPTNO1100ALLEN102101CLARK20
A full outer join between left table DEPT and right table EMP, based on an equijoin join condition involving columns DEPTNO in DEPT and DEPTNO in EMP, returns the following result set.
ROW #EMPNOENAMEEMP.DEPTNODEPT.DEPTNODNAME1100ALLEN1010SALES2101CLARK20NULLNULL3NULLNULL3030MARKET
In the result set, row 1 represents a join between row 1 of EMP and row 1 of DEPT. Row 2 is a “right” outer join row because it was returned for a row which did not satisfy the join condition with any row from the left table. Row 2 in particular represents row 2 of EMP. Note the columns of the left table contain NULL. In this case, DEPT.DEPTNO and DNAME of table DEPT contains NULL.
Row 3 is a “left” outer join row for row 2 in table DEPT, which did not match any row from right table EMP.
Described herein are techniques for efficiently computing full outer joins between tables. The term table refers generally to any set of rows or tuples such as those stored in a database table or computed for an expression, such as a query or subquery. For example, the rows in the result set above can be referred to as a table.